#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007
class Solution {
public:
    std::array<int,100000> arr;
    int numDecodings(std::string s) {
        arr.fill(0);
        int n = s.size();
        arr[n] = 1;
        for (int i=n-1; i>=0; i--)
        {
            if (s[i]=='0')
            {
                arr[i] = 0;
                continue;
            }
    
            arr[i]+=arr[i+1];
            if (i+1<s.size()&&(s[i]-'0')*10+s[i+1]-'0'<=26)
            {
                arr[i] +=arr[i+2];
            }
        }
        return arr[0];
    }
    int f(int i,std::string & s)
    {
        if (i==s.size())
        {
            return 1;
        }
        if (s[i]=='0') return 0;
        if (arr[i]!=std::numeric_limits<int>::max()) return arr[i];
        int ans = 0;
        ans += f(i+1,s);
        if (i+1<s.size()&&(s[i]-'0')*10+s[i+1]-'0'<=26)
        {
            ans += f(i+2,s);
        }
        arr[i] = ans;
        return ans;
    }
};